package ru.ifmo.ctddev.larionov.task2;

import java.util.*;

public class Bag<T extends Comparable<? super T>> extends AbstractCollection<T> {

	private NavigableMap<T, List<T>> map;
	private int size;
	private int currentRevision;

	public Bag() {
		map = new TreeMap<T, List<T>>();
		currentRevision = 0;
	}

	public Iterator<T> iterator() {
		return new BagIterator(false);
	}

	public Iterator<T> reverseIterator() {
		return new BagIterator(true);
	}

	public boolean add(T e) {
		if (!map.containsKey(e)) {
			map.put(e, new LinkedList<T>());
		}

		map.get(e).add(e);
		++size;
		++currentRevision;
		return true;
	}

	public void clear() {
		map.clear();
		size = 0;
		++currentRevision;
	}

	public boolean contains(Object o) {
		return map.containsKey(o);
	}

	public boolean remove(Object o) {
		if (!map.containsKey(o)) {
			return false;
		}

		map.get(o).remove(o);

		if (map.get(o).isEmpty()) {
			map.remove(o);
		}

		--size;
		++currentRevision;
		return true;
	}

	public int size() {
		return size;
	}

	private class BagIterator implements Iterator<T> {

		private Iterator<Map.Entry<T, List<T>>> mapIterator;
		private Iterator<T> listIterator;
		private Map.Entry<T, List<T>> lastNext;
		private int currentIteratorRevision;

		public BagIterator(boolean l) {
			if (l) {
				mapIterator = map.descendingMap().entrySet().iterator();
			} else {
				mapIterator = map.entrySet().iterator();
			}

			lastNext = null;
			currentIteratorRevision = currentRevision;
		}

		private boolean isIteratorValid() {
			return currentIteratorRevision == currentRevision;
		}

		public boolean hasNext() {
			if (!isIteratorValid()) {
				throw new ConcurrentModificationException();
			}

			return mapIterator.hasNext()
					|| (listIterator != null && listIterator.hasNext());
		}

		public T next() {
			if (!isIteratorValid()) {
				throw new ConcurrentModificationException();
			}

			if (listIterator == null || !listIterator.hasNext()) {
				lastNext = mapIterator.next();
				listIterator = lastNext.getValue().iterator();
			}

			return listIterator.next();
		}

		public void remove() {
			if (!isIteratorValid()) {
				throw new ConcurrentModificationException();
			}
			if (lastNext == null) {
				throw new IllegalStateException();
			}

			listIterator.remove();

			if (lastNext.getValue().isEmpty()) {
				mapIterator.remove();
			}

			--size;
		}
	}
}